{ "cells": [ { "metadata": {}, "cell_type": "markdown", "source": [ "# Interactive Simplex Tableau\n", "\n", "## Try me\n", "[![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/CLP/tutorials/Simplex%20-%20Interactive%20Tableau.ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FCLP%2Ftutorials%2FSimplex%20-%20Interactive%20Tableau.ipynb)\n", "\n", "## Introduction\n", "## Interactive Simplex Tableau Activity\n", "\n", "In this activity, we will **walk through the Simplex algorithm step by step**, exactly as it is done on the board, but using an interactive computational notebook to make each transformation explicit and traceable.\n", "\n", "Rather than treating Simplex as a “black box” that jumps directly to the optimal solution, this notebook lets you **control the algorithm iteration by iteration**: selecting the entering variable from the *z-row*, applying the *ratio test* (with ratios shown explicitly), performing the pivot operation, and observing how the tableau evolves at each step.\n", "\n", "At every iteration, the notebook:\n", "- displays the current tableau in a readable form,\n", "- briefly explains *why* each decision is made,\n", "- and pauses execution so you can reflect before moving on.\n", "\n", "The goal is not speed, but **understanding**. By interacting with the tableau and seeing how algebraic operations translate into algorithmic steps, you will build an intuition for:\n", "- why the Simplex method works,\n", "- how feasibility and optimality are maintained,\n", "- and how local decisions in the tableau drive the global optimization process.\n", "\n", "Think of this notebook as a **guided conversation with the Simplex algorithm**: you ask it to take the next step, and it shows you exactly what it is doing and why." ], "id": "cfa693c4396fdc59" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## How to Use This Notebook\n", "### Instructions\n", "Please follow this workflow:\n", "\n", "1. **Run cells from top to bottom**\n", " Make sure you execute each cell in order so that the Simplex functions and the initial tableau are properly defined, it is important that you run the first code cell that defines the SimplesStepper class we will use to run the Simplex.\n", "\n", "2. **Read before running the next step**\n", " After each Simplex iteration, the notebook explains what decision is being made (entering variable, ratio test, pivot).\n", " Take a moment to understand *why* that step is valid.\n", "\n", "3. **Advance one iteration at a time**\n", " The algorithm pauses after each iteration.\n", " Press **Enter** only when you are ready to move on.\n", "\n", "4. **Focus on the logic, not the arithmetic**\n", " The goal is not to memorize row operations, but to understand:\n", " - why a variable enters the basis,\n", " - why another one leaves,\n", " - and how these choices move the solution toward optimality.\n", " Try to predict the understand the decisions.\n", "\n", "5. **Ask yourself at each step**\n", " - Why is this variable entering?\n", " - What does the ratio test guarantee?\n", " - How is feasibility preserved after the pivot?\n", " - Remember what happens with the Simplex, the analogies with the graphical method.\n", "\n", "If something feels unclear, stop and discuss it — this notebook is meant to support **reasoning**, not to rush to the final answer.\n", "### Pre-requirements\n", "#### Google Colabs\n", "You do not need to install anything, everything works off-the-shelf in Google Colabs\n", "#### Binder\n", "In a fresh Jupyter Notebook environment, you need to install Numpy and Pandas. Create a new cell and run this code:\n", "```shell\n", "!pip install pandas\n", "!pip install numpy\n", "```" ], "id": "f704fd021d222bb6" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Simplex Stepper Initialization\n", "Run this cell to initialize the ```Simplex Stepper``` class that we will use throughout the activity." ], "id": "63a1f6c0d1720b03" }, { "metadata": { "ExecuteTime": { "end_time": "2026-01-03T17:39:35.975340Z", "start_time": "2026-01-03T17:39:35.967778Z" } }, "cell_type": "code", "source": [ "import numpy as np\n", "import pandas as pd\n", "from dataclasses import dataclass, field\n", "from IPython.display import display, Markdown\n", "\n", "@dataclass\n", "class SimplexStepper:\n", " \"\"\"\n", " Tableau conventions:\n", " - Row 0 = objective (z) row\n", " - Column z_col = z column (typically 0), with tableau[0, z_col] = 1\n", " - Last column = RHS\n", " - Constraint rows = 1..(m)\n", " - Pivoting is standard Gauss-Jordan on (leaving_row, entering_col)\n", "\n", " Default pivot rule (common in many OR courses):\n", " - Entering variable: most negative coefficient in the objective row\n", " (excluding z column and RHS)\n", " - Optimal if all objective-row coefficients (excluding z and RHS) >= 0\n", " \"\"\"\n", " tableau: np.ndarray\n", " row_labels: list = field(default_factory=list)\n", " col_labels: list = field(default_factory=list)\n", "\n", " z_col: int = 0\n", " rhs_col: int = None # if None => last column\n", " iteration_count: int = 0\n", " history: list = field(default_factory=list)\n", "\n", " @classmethod\n", " def from_numpy(cls, arr, row_labels=None, col_labels=None, z_col=0, rhs_col=None):\n", " T = np.array(arr, dtype=float)\n", " return cls(T, row_labels or [], col_labels or [], z_col=z_col, rhs_col=rhs_col)\n", "\n", " @classmethod\n", " def from_dataframe(cls, df: pd.DataFrame, z_col=0, rhs_col=None):\n", " T = df.to_numpy(dtype=float)\n", " return cls(T, list(df.index), list(df.columns), z_col=z_col, rhs_col=rhs_col)\n", "\n", " def _rhs(self):\n", " return (self.tableau.shape[1] - 1) if self.rhs_col is None else self.rhs_col\n", "\n", " def as_dataframe(self) -> pd.DataFrame:\n", " df = pd.DataFrame(self.tableau.copy())\n", " if self.row_labels:\n", " df.index = self.row_labels\n", " if self.col_labels:\n", " df.columns = self.col_labels\n", " return df\n", "\n", " def show(self, title=None, note=None, highlight=None, ratio=None):\n", " if title:\n", " display(Markdown(f\"### {title}\"))\n", " if note:\n", " display(Markdown(note))\n", "\n", " df = self.as_dataframe().round(4)\n", " if ratio is not None:\n", " df['Ratio'] = ratio\n", " display(df)\n", "\n", " if highlight is not None:\n", " r, c = highlight\n", " r_name = self.row_labels[r] if self.row_labels else str(r)\n", " c_name = self.col_labels[c] if self.col_labels else str(c)\n", " display(Markdown(f\"**Pivot position:** row `{r_name}`, column `{c_name}`\"))\n", "\n", " # ---------------- simplex logic ----------------\n", " def _objective_coeffs_view(self):\n", " \"\"\"\n", " Return objective row coefficients excluding z column and RHS.\n", " \"\"\"\n", " rhs = self._rhs()\n", " cols = [j for j in range(self.tableau.shape[1]) if j not in (self.z_col, rhs)]\n", " return self.tableau[0, cols], cols\n", "\n", " def is_optimal(self, tol=1e-9):\n", " coeffs, _ = self._objective_coeffs_view()\n", " return np.all(coeffs >= -tol)\n", "\n", " def choose_entering_variable(self, tol=1e-9):\n", " \"\"\"\n", " Most negative in objective row (excluding z and RHS).\n", " Returns column index or None if optimal.\n", " \"\"\"\n", " coeffs, cols = self._objective_coeffs_view()\n", " min_val = np.min(coeffs)\n", " if min_val >= -tol:\n", " return None\n", " return cols[int(np.argmin(coeffs))]\n", "\n", " def choose_leaving_variable(self, entering_col, tol=1e-9):\n", " \"\"\"\n", " Min ratio test over constraint rows (rows 1..end).\n", " Only rows with positive entry in entering column are candidates.\n", " \"\"\"\n", " rhs = self._rhs()\n", " col = self.tableau[1:, entering_col]\n", " b = self.tableau[1:, rhs]\n", "\n", " valid = col > tol\n", " if not np.any(valid):\n", " return None, None # unbounded\n", "\n", " ratios = np.full_like(b, np.inf, dtype=float)\n", " ratios[valid] = b[valid] / col[valid]\n", " leaving_in_constraints = int(np.argmin(ratios))\n", " print(ratios)\n", " # add a zero in first row of ratio to match index size\n", " ratios = np.insert(ratios, 0, 0, axis=0)\n", " print(ratios)\n", " return leaving_in_constraints + 1, ratios # shift because constraints start at row 1\n", "\n", " def pivot(self, pivot_row, pivot_col, tol=1e-12):\n", " T = self.tableau\n", " p = T[pivot_row, pivot_col]\n", " if abs(p) < tol:\n", " raise ValueError(\"Pivot element too close to zero.\")\n", "\n", " T[pivot_row, :] = T[pivot_row, :] / p\n", " for r in range(T.shape[0]):\n", " if r == pivot_row:\n", " continue\n", " factor = T[r, pivot_col]\n", " if abs(factor) > tol:\n", " T[r, :] = T[r, :] - factor * T[pivot_row, :]\n", "\n", " def step(self, tol=1e-9, pause=True):\n", " self.iteration_count += 1\n", " self.history.append(self.tableau.copy())\n", "\n", " # 1) optimality\n", " if self.is_optimal(tol=tol):\n", " self.show(\n", " title=f\"Iteration {self.iteration_count} - Step 0: Optimality check\",\n", " note=\"All objective-row coefficients (excluding **z** and **RHS**) are **non-negative** → ✅ **optimal**.\"\n", " )\n", " return \"optimal\"\n", "\n", " # 2) entering\n", " entering = self.choose_entering_variable(tol=tol)\n", " enter_name = self.col_labels[entering] if self.col_labels else f\"col {entering}\"\n", " self.show(\n", " title=f\"Iteration {self.iteration_count} - Step 1: Choose entering variable\",\n", " note=f\"Pick the **most negative** coefficient in the objective row → entering variable is **{enter_name}**.\",\n", " )\n", "\n", " # 3) leaving\n", " leaving, ratios = self.choose_leaving_variable(entering, tol=tol)\n", " if leaving is None:\n", " self.show(\n", " title=f\"Iteration {self.iteration_count} - Step 2: Ratio test\",\n", " note=f\"No positive entries in column **{enter_name}** among constraints → ⚠️ **unbounded**.\"\n", " )\n", " return \"unbounded\"\n", "\n", " leave_name = self.row_labels[leaving] if self.row_labels else f\"row {leaving}\"\n", " self.show(\n", " title=f\"Iteration {self.iteration_count} - Step 2: Choose leaving row (ratio test)\",\n", " note=f\"Apply minimum ratio test (RHS / positive pivot-column entry) → leaving row is **{leave_name}**.\",\n", " highlight=(leaving, entering),\n", " ratio=ratios\n", " )\n", "\n", " # 4) pivot\n", " self.pivot(leaving, entering)\n", " self.show(\n", " title=f\"Iteration {self.iteration_count} - Step 3: Pivot\",\n", " note=\"Normalize pivot row, eliminate pivot column from all other rows. Tableau updated.\",\n", " highlight=(leaving, entering),\n", " )\n", "\n", " if pause:\n", " input(\"Press Enter to continue...\")\n", "\n", " return \"continue\"\n", "\n", " def run(self, max_steps=50, tol=1e-9, pause=True):\n", " for _ in range(max_steps):\n", " status = self.step(tol=tol, pause=pause)\n", " if status in (\"optimal\", \"unbounded\"):\n", " return status\n", " return \"max_steps\"" ], "id": "737e906f6cce65f7", "outputs": [], "execution_count": 15 }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Tableau Initialization\n", "The Simplex algorithm works on a **tableau representation** of the CLP problem.\n", "In this notebook, the tableau is stored as a NumPy array called `T0`.\n", "\n", "### Structure of the Tableau\n", "The Tableau follows the same conventions as the Tableaus in other tutorials of this interactive book:\n", "- **Rows** represent equations of the problem model:\n", " - Row `0`: is the objective function (or *z-row*)\n", " - Rows `1..m`: represent the constraints\n", "- **Columns** contain the coefficients for each problem variable ($z$, $x_1$, $x_2$, ..., $s_1$, $s_2$, ...):\n", " - The first column contains the coefficients for the objective variable $z$ (1 in the objective function, and 0 for the rest of equations)\n", " - Next we add the columns corresponding to decision variables\n", " - And finally, coefficients for slacks or artificial variables\n", " - The last column contains the **RHS** coefficients\n", "\n", "#### Sign convention\n", "The problem needs to be converted to a **standard maximization problem**:\n", "- Objective coefficients appear **negated** in the z-row\n", " (e.g. maximize `3x₁ + 2x₂` → z-row contains `-3, -2`)\n", "- Constraint right-hand sides must be **non-negative**\n", "\n", "#### Example\n", "For instance, the following problem:\n", "\n", "$\\max z = 3*x_1 + 2*x_2$\n", "\n", "s.t.\n", "$x_1 + x_2 \\leq 4$\n", "\n", "$2*x_1 + x_2 \\leq 5$\n", "\n", "results in the following Numpy array:\n", "\n", "```python\n", "T0 = np.array([\n", " # z x1 x2 s1 s2 RHS\n", " [ 1, -3, -2, 0, 0, 0], # objective (z-row)\n", " [ 0, 1, 1, 1, 0, 4], # constraint 1\n", " [ 0, 2, 1, 0, 1, 5], # constraint 2\n", "], dtype=float)\n", "```\n", "\n", "### Labels\n", "We use labels to make the Tableau easier to interpret.\n", "- **Row labels**: label each equation. Normally we label the objective function with ```\"z\"```. You can use representative labels for the constraints\n", "- **Column labels**: Label each variable, for instance, ```\"x1\"``` for $x_1$, and so forth. Remember that the first column is reserved for $z$ and the last one for the $RHS$, so label accordingly!\n", "\n", "For instance, for the same example above, we would define the following labels:\n", "\n", "```python\n", "row_labels = [\"z\", \"c1\", \"c2\"]\n", "col_labels = [\"z\", \"x1\", \"x2\", \"s1\", \"s2\", \"RHS\"]\n", "```\n", "\n", "### Simplex Stepper Initialization\n", "Once you have created your Numpy model and your labels, you just need to instantiate the stepper. To check everything worked, use the method ```show()``` to display the initial Tableau (should be the same you created!)\n", "\n", "```python\n", "simp = SimplexStepper.from_numpy(T0, row_labels=row_labels, col_labels=col_labels, z_col=0)\n", "simp.show(title=\"Initial tableau (z row first)\")\n", "```" ], "id": "2c17f89ac0813359" }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Example\n", "\n", "### Initialization\n", "This is the same example in previous tutorials, you can edit it replace the initial Tableau with a different problem instance.\n", "\n" ], "id": "d6768c70bbc15e04" }, { "metadata": { "ExecuteTime": { "end_time": "2026-01-03T18:31:20.970660Z", "start_time": "2026-01-03T18:31:20.964919Z" } }, "cell_type": "code", "source": [ "M = 1e6 # Large number just in case it is needed for constraints of type equal\n", "\n", "T0 = np.array([\n", " # z x1 x2 s1 s2 s3 RHS\n", " [ 1, -300, -250, 0, 0, 0, 0], # objective row (maximize 3x1+2x2)\n", " [ 0, 2, 1, 1, 0, 0, 40], # constraints\n", " [ 0, 1, 3, 0, 1, 0, 45],\n", " [0, 1, 0, 0, 0, 1, 12]\n", "], dtype=float)\n", "\n", "row_labels = [\"z\", \"c1\", \"c2\", \"c3\"]\n", "col_labels = [\"z\", \"x1\", \"x2\", \"s1\", \"s2\", \"s3\", \"RHS\"]\n", "\n", "simp = SimplexStepper.from_numpy(T0, row_labels=row_labels, col_labels=col_labels, z_col=0)\n", "simp.show(title=\"Initial tableau (z row first)\")" ], "id": "bbda7cf0bb8a9443", "outputs": [ { "data": { "text/plain": [ "" ], "text/markdown": "### Initial tableau (z row first)" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ " z x1 x2 s1 s2 s3 RHS\n", "z 1.0 -300.0 -250.0 0.0 0.0 0.0 0.0\n", "c1 0.0 2.0 1.0 1.0 0.0 0.0 40.0\n", "c2 0.0 1.0 3.0 0.0 1.0 0.0 45.0\n", "c3 0.0 1.0 0.0 0.0 0.0 1.0 12.0" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
zx1x2s1s2s3RHS
z1.0-300.0-250.00.00.00.00.0
c10.02.01.01.00.00.040.0
c20.01.03.00.01.00.045.0
c30.01.00.00.00.01.012.0
\n", "
" ] }, "metadata": {}, "output_type": "display_data" } ], "execution_count": 20 }, { "metadata": {}, "cell_type": "markdown", "source": "", "id": "227f67ec0a347840" }, { "metadata": { "ExecuteTime": { "end_time": "2026-01-03T18:31:35.628022Z", "start_time": "2026-01-03T18:31:30.621570Z" } }, "cell_type": "code", "source": [ "while True:\n", " status = simp.step(pause=True)\n", " if status != \"continue\":\n", " print(\"Status:\", status)\n", " break" ], "id": "dbfebff527f6c58a", "outputs": [ { "data": { "text/plain": [ "" ], "text/markdown": "### Iteration 1 - Step 1: Choose entering variable" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "Pick the **most negative** coefficient in the objective row → entering variable is **x1**." }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ " z x1 x2 s1 s2 s3 RHS\n", "z 1.0 -300.0 -250.0 0.0 0.0 0.0 0.0\n", "c1 0.0 2.0 1.0 1.0 0.0 0.0 40.0\n", "c2 0.0 1.0 3.0 0.0 1.0 0.0 45.0\n", "c3 0.0 1.0 0.0 0.0 0.0 1.0 12.0" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
zx1x2s1s2s3RHS
z1.0-300.0-250.00.00.00.00.0
c10.02.01.01.00.00.040.0
c20.01.03.00.01.00.045.0
c30.01.00.00.00.01.012.0
\n", "
" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "[20. 45. 12.]\n", "[ 0. 20. 45. 12.]\n" ] }, { "data": { "text/plain": [ "" ], "text/markdown": "### Iteration 1 - Step 2: Choose leaving row (ratio test)" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "Apply minimum ratio test (RHS / positive pivot-column entry) → leaving row is **c3**." }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ " z x1 x2 s1 s2 s3 RHS Ratio\n", "z 1.0 -300.0 -250.0 0.0 0.0 0.0 0.0 0.0\n", "c1 0.0 2.0 1.0 1.0 0.0 0.0 40.0 20.0\n", "c2 0.0 1.0 3.0 0.0 1.0 0.0 45.0 45.0\n", "c3 0.0 1.0 0.0 0.0 0.0 1.0 12.0 12.0" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
zx1x2s1s2s3RHSRatio
z1.0-300.0-250.00.00.00.00.00.0
c10.02.01.01.00.00.040.020.0
c20.01.03.00.01.00.045.045.0
c30.01.00.00.00.01.012.012.0
\n", "
" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "**Pivot position:** row `c3`, column `x1`" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "### Iteration 1 - Step 3: Pivot" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "Normalize pivot row, eliminate pivot column from all other rows. Tableau updated." }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ " z x1 x2 s1 s2 s3 RHS\n", "z 1.0 0.0 -250.0 0.0 0.0 300.0 3600.0\n", "c1 0.0 0.0 1.0 1.0 0.0 -2.0 16.0\n", "c2 0.0 0.0 3.0 0.0 1.0 -1.0 33.0\n", "c3 0.0 1.0 0.0 0.0 0.0 1.0 12.0" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
zx1x2s1s2s3RHS
z1.00.0-250.00.00.0300.03600.0
c10.00.01.01.00.0-2.016.0
c20.00.03.00.01.0-1.033.0
c30.01.00.00.00.01.012.0
\n", "
" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "**Pivot position:** row `c3`, column `x1`" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "### Iteration 2 - Step 1: Choose entering variable" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "Pick the **most negative** coefficient in the objective row → entering variable is **x2**." }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ " z x1 x2 s1 s2 s3 RHS\n", "z 1.0 0.0 -250.0 0.0 0.0 300.0 3600.0\n", "c1 0.0 0.0 1.0 1.0 0.0 -2.0 16.0\n", "c2 0.0 0.0 3.0 0.0 1.0 -1.0 33.0\n", "c3 0.0 1.0 0.0 0.0 0.0 1.0 12.0" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
zx1x2s1s2s3RHS
z1.00.0-250.00.00.0300.03600.0
c10.00.01.01.00.0-2.016.0
c20.00.03.00.01.0-1.033.0
c30.01.00.00.00.01.012.0
\n", "
" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "[16. 11. inf]\n", "[ 0. 16. 11. inf]\n" ] }, { "data": { "text/plain": [ "" ], "text/markdown": "### Iteration 2 - Step 2: Choose leaving row (ratio test)" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "Apply minimum ratio test (RHS / positive pivot-column entry) → leaving row is **c2**." }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ " z x1 x2 s1 s2 s3 RHS Ratio\n", "z 1.0 0.0 -250.0 0.0 0.0 300.0 3600.0 0.0\n", "c1 0.0 0.0 1.0 1.0 0.0 -2.0 16.0 16.0\n", "c2 0.0 0.0 3.0 0.0 1.0 -1.0 33.0 11.0\n", "c3 0.0 1.0 0.0 0.0 0.0 1.0 12.0 inf" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
zx1x2s1s2s3RHSRatio
z1.00.0-250.00.00.0300.03600.00.0
c10.00.01.01.00.0-2.016.016.0
c20.00.03.00.01.0-1.033.011.0
c30.01.00.00.00.01.012.0inf
\n", "
" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "**Pivot position:** row `c2`, column `x2`" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "### Iteration 2 - Step 3: Pivot" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "Normalize pivot row, eliminate pivot column from all other rows. Tableau updated." }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ " z x1 x2 s1 s2 s3 RHS\n", "z 1.0 0.0 0.0 0.0 83.3333 216.6667 6350.0\n", "c1 0.0 0.0 0.0 1.0 -0.3333 -1.6667 5.0\n", "c2 0.0 0.0 1.0 0.0 0.3333 -0.3333 11.0\n", "c3 0.0 1.0 0.0 0.0 0.0000 1.0000 12.0" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
zx1x2s1s2s3RHS
z1.00.00.00.083.3333216.66676350.0
c10.00.00.01.0-0.3333-1.66675.0
c20.00.01.00.00.3333-0.333311.0
c30.01.00.00.00.00001.000012.0
\n", "
" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "**Pivot position:** row `c2`, column `x2`" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "### Iteration 3 - Step 0: Optimality check" }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "" ], "text/markdown": "All objective-row coefficients (excluding **z** and **RHS**) are **non-negative** → ✅ **optimal**." }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ " z x1 x2 s1 s2 s3 RHS\n", "z 1.0 0.0 0.0 0.0 83.3333 216.6667 6350.0\n", "c1 0.0 0.0 0.0 1.0 -0.3333 -1.6667 5.0\n", "c2 0.0 0.0 1.0 0.0 0.3333 -0.3333 11.0\n", "c3 0.0 1.0 0.0 0.0 0.0000 1.0000 12.0" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
zx1x2s1s2s3RHS
z1.00.00.00.083.3333216.66676350.0
c10.00.00.01.0-0.3333-1.66675.0
c20.00.01.00.00.3333-0.333311.0
c30.01.00.00.00.00001.000012.0
\n", "
" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "Status: optimal\n" ] } ], "execution_count": 21 }, { "metadata": {}, "cell_type": "markdown", "source": [ "## Guided Activity\n", "### Choose Problem\n", "Choose a problem with 2 decision variables that is solved with the graphical method. You can use a problem you have defined and solved or alternatively select one instance from the problems solved with the graphical method in the interactive book tutorial [Graphical Method](graphic-solution-extended.ipynb).\n", "\n", "Once you have chosen your problem, complete the following questions.\n", "\n", "1. **Convert the problem into the standard form.**\n", "Remember the steps:\n", "- Convert all the constraints to equalities introducing slack variables (or artificial variables)\n", "- Ensure RHS are greater than zero and that problem is of type *maximize*.\n", "\n", "The following cell provides a Markdown template you can use to edit your model, just double-click and update the coefficients in the objective function and constraints.\n" ], "id": "b3c736be95df3a2" }, { "metadata": {}, "cell_type": "markdown", "source": [ "**Objective function** (substitute the coefficients $c_1$ and $c_2$ with your coefficients).\n", "\n", "$z = c_1*x_1 + c_2*x_2$\n", "\n", "subject to: (substitute the LHS coefficients and RHS coefficients with your own)\n", "\n", "$a_{11}*x_1 + a_{12}*x_2 + s_1 = b_1$\n", "\n", "$a_{21}*x_1 + a_{22}*x_2 + s_2 = b_2$\n", "\n", "$a_{31}*x_1 + a_{32}*x_2 + s_3 = b_3$\n", "\n", "(copy and paste if you need more)\n" ], "id": "bce89c596a0c54dd" }, { "metadata": {}, "cell_type": "markdown", "source": "2. **Define the Tableau** Check the example and fill in and run the following cell to define the Tableau for your model.", "id": "e52f972f0b354ffe" }, { "metadata": {}, "cell_type": "code", "outputs": [], "execution_count": null, "source": [ "M = 1e6 # Large number just in case it is needed for constraints of type equal\n", "\n", "T0 = np.array([\n", " # TODO: Add the objective row (e.g. maximize 3x1+2x2)\n", " # TODO: Add the constraints and RHS\n", "], dtype=float)\n", "\n", "# TODO: Edit your labels\n", "row_labels = []\n", "col_labels = []\n", "\n" ], "id": "ba263f1142c850f9" }, { "metadata": {}, "cell_type": "markdown", "source": "Once you have defined your Tableau. Instantiate the simplex:", "id": "c93755db7772bf00" }, { "metadata": {}, "cell_type": "code", "outputs": [], "execution_count": null, "source": [ "simp = SimplexStepper.from_numpy(T0, row_labels=row_labels, col_labels=col_labels, z_col=0)\n", "simp.show(title=\"Initial tableau (z row first)\")" ], "id": "aa0625b9c5d9430" }, { "metadata": {}, "cell_type": "markdown", "source": [ "3. **Run the Simplex.** Use the following cell to run the Simplex: For each iteration, identify the vertex of the feasibility region visited by the algorithm in the graph. Use the last Markdown cell to write down the values of the decision variables and objective variables at each vertex visited. At every iteration, answer the following questions:\n", "- What is the entering variable? Why is that entering variable improving the objective in your sign convention?\n", "- Which edge of the feasible region are you moving along?\n", "- What does the ratio test guarantee geometrically (in terms of feasibility in that specific direction)?\n", "- Which constraint becomes active when the leaving variable leaves the basis?" ], "id": "847c35e49e0a6b10" }, { "metadata": {}, "cell_type": "code", "outputs": [], "execution_count": null, "source": [ "while True:\n", " status = simp.step(pause=True)\n", " if status != \"continue\":\n", " print(\"Status:\", status)\n", " break" ], "id": "54b8e5359c277306" }, { "metadata": {}, "cell_type": "markdown", "source": [ "**Initial Tableau**\n", "z: 0, $x_1$: 0, $x_2$: 0, $s_1$: ?, $s_2$: ?, $s_3$: ?\n", "**Iteration 1**\n", "Complete!\n" ], "id": "3c6e1db8b94ab492" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.6" } }, "nbformat": 4, "nbformat_minor": 5 }